/**
 * 剑指 Offer 14- II. 剪绳子 II
 * https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
 */
public class Solutions_Offer_14_II {
    public static void main(String[] args) {
//        int n = 2;  // output: 1 * 2 = 1
//        int n = 10;  // output: 3 * 3 * 4 = 36
        int n = 127;  // output: 439254203

        int result = cuttingRope(n);
        System.out.println(result);
    }

    /**
     * 大数计算的方式：每一步都进行一次取模，直接计算出最终结果再取余的方式，将在计算过程中数值溢出
     * 根据证明：每步取余与最终的结果取余，结果将不变
     *
     * 81 % 17 = 13  (17 * 4 = 68、68 - 81 = -13)
     * 而 3 * 3 * 3 * 3 = 81 的计算过程中，可以证明：
     * 3 * 3 % 17 = 9
     * 9 * 3 % 17 = 10
     * 10 * 3 % 17 = 13
     */
    public static int cuttingRope(int n) {
        int mod = 1_000_000_007;
        if (n <= 3) {
            return n - 1;
        }

        long res = 1;
        while (n > 4) {
            res = res * 3 % mod;
            n -= 3;
        }
        return (int) (res * n % mod);
    }
}
